package leetcode;

import sort.MaoPaoSort;


public class BeautifulArragment {

	public static void main(String[] args) {
		BeautifulArragment object = new BeautifulArragment();
		System.out.println(object.countArrangement(4));
	}
	
	private int total = 0;
	public int countArrangement(int N) {
        total = 0;
        int[] nums = new int[N + 1];
        for(int i = 0; i < nums.length; i++){
        	nums[i] = i;
        }
        arrange(nums, 1);
        return total;
    }

	public void arrange(int n , int start){
		if(start == n + 1){
			total++;
			return;
		}
		for(int i = start; i <= n; i++){
			//什么情况下可以交换呢，就是 i % j == 0的时候
			if(i % start == 0){
				arrange(n, start + 1);
			}
		}
	}
	
	
	//runtime为54ms，竟然还有2ms的
	public void arrange(int[] nums , int start){
		if(start == nums.length){
			total++;
			for (int i = 0; i < nums.length; i++){
                System.out.print(nums[i] + " ");
			}
            System.out.println();
			return;
		}
		for(int i = start; i < nums.length; i++){
			//什么情况下可以交换呢，就是两个数可以整除的时候
			//注意不能写成nums[i] % nums[start] == 0，因为1 2 3
			//比如将2和1交换之后，那么会变成 2 1 3
			//此时3和1可以整除，交换 变成2 3 1
			//所以应该判断nums[i] % start;
			if(nums[i] % start == 0 || start % nums[i] == 0){
//			if(nums[start] % start == 0 || start % nums[start] == 0){
				swap(nums, i, start);
				arrange(nums, start + 1);
				//复原
				swap(nums, i, start);
			}
		}
	}
	
	public void swap(int[] nums, int i, int j){
		int temp = nums[i];
		nums[i]= nums[j];
		nums[j] = temp;
	}
}
